#include <bits/stdc++.h>
#include "Element.cc"
using namespace std;
const double MIN_r = 0;
const double MAX_r = 1e+20;
// random_device rd;
default_random_engine eng(time(nullptr));
uniform_real_distribution<double> distr(MIN_r, MAX_r);

/** @class 存储的Element均不相同*/
class Treap {
private:
    struct TreeNode {
    public:
        Element e;
        TreeNode *father, *left, *right;
        double priorty;//越小优先级越高
        TreeNode(const Element &_e) :father(nullptr), left(nullptr), right(nullptr) {
            e = _e;
            priorty = distr(eng);
        }
        TreeNode(const TreeNode &node) :father(node.father), left(node.left), right(node.right) {
            e = node.e;
            priorty = distr(eng);
        }
    }*root;
    int size_;
    /// @brief 
    ProcessElement processfunction;
    void turnLeft(TreeNode *node);
    void turnRight(TreeNode *node);
    void floatup(TreeNode *node);
    void sinkdown(TreeNode *node);
    void helperInorderTravel(const TreeNode *const treenode);
    void postorderDelete(TreeNode *treenode);
public:
    Treap();
    bool insert(const Element &e);
    bool erase(const Element &e);
    void InorderTravel(ProcessElement f);
    ~Treap();
};


int main() {
    stack<Treap *> stack_treap;
    Treap *nowtreap = nullptr;
    while (!cin.eof()) {
        string line_string;
        getline(cin, line_string);
        stringstream line_input(line_string);
        string op;
        line_input >> op;
        if (op == "Treap" || op == "new") {
            nowtreap = new Treap();
            stack_treap.push(nowtreap);
        }
        else if (!nowtreap) {
            continue;
        }
        else if (op == "insert") {
            int id;
            line_input >> id;
            cout << nowtreap->insert(Element(id)) << endl;
        }
        else if (op == "erase") {
            int id;
            line_input >> id;
            cout << nowtreap->erase(Element(id)) << endl;
        }
        else if (op == "delete") {
            stack_treap.pop();
            delete nowtreap;
            if (stack_treap.empty()) { nowtreap = nullptr; }
            else { nowtreap = stack_treap.top(); }
        }
        else if (op == "print") {
            nowtreap->InorderTravel(printElement);
            cout << endl;
        }
    }
    //system("pause");
    return 0;
}


Treap::Treap(/* args */) {
    root = nullptr;
    processfunction = nullptr;
    size_ = 0;
}

bool Treap::insert(const Element &e) {
    TreeNode **pos = &root, *F = nullptr;
    while (*pos) {
        F = *pos;
        if ((*pos)->e < e) {
            pos = &((*pos)->right);

        }
        else if ((*pos)->e == e)
            return false;
        else {
            pos = &((*pos)->left);
        }
    }
    *pos = new TreeNode(e);
    (*pos)->father = F;
    floatup(*pos);
    ++size_;
    return true;
}

bool Treap::erase(const Element &e) {
    TreeNode **pos = &root;
    while (*pos) {
        if ((*pos)->e < e) pos = &((*pos)->right);
        else if ((*pos)->e == e) break;
        else pos = &((*pos)->left);
    }
    if (*pos) {
        sinkdown(*pos);
        TreeNode *F = (*pos)->father;
        if (!F) { ; }
        else if (F->left == *pos) { F->left = nullptr; }
        else if (F->right == *pos) { F->right = nullptr; }
        delete *pos;
        *pos = nullptr;
        --size_;
        return true;
    }
    return false;
}
/**
 * @param pnode 需要左转的节点
*/
void Treap::turnLeft(TreeNode *node) {
    if (!node->right) return;
    TreeNode *sonr = node->right;
    TreeNode *F = node->father;

    node->right = sonr->left;
    if (sonr->left) sonr->left->father = node;
    sonr->left = node;

    sonr->father = F;
    if (!F) {
        root = sonr;
        return;
    }
    if (F->e > sonr->e) {
        F->left = sonr;
    }
    else {
        F->right = sonr;
    }

}
/**
 * @param pnode 需要右转的节点
*/
void Treap::turnRight(TreeNode *node) {
    if (!node->left) return;
    TreeNode *sonl = node->left;
    TreeNode *F = node->father;

    node->left = sonl->right;
    if (sonl->right) sonl->right->father = node;
    sonl->right = node;


    sonl->father = F;
    if (!F) {
        root = sonl;
        return;
    }
    if (F->left == node) {
        F->left = sonl;
    }
    else {
        F->right = sonl;
    }
}

void Treap::floatup(TreeNode *node) {
    TreeNode *F = node->father;
    for (;F && node->priorty < F->priorty;F = node->father) {
        if (F->right == node) {
            // node 从father的右边来
            turnLeft(F);
        }
        else {
            turnRight(F);
        }
    }
}

void Treap::sinkdown(TreeNode *node) {
    for (TreeNode *sl = node->left, *sr = node->right; sl || sr; sl = node->left, sr = node->right) {
        bool isturnLeft = (sr && (!sl || sr->priorty < sl->priorty));
        isturnLeft ? turnLeft(node) : turnRight(node);
    }
}

void Treap::helperInorderTravel(const TreeNode *const treenode) {
    if (treenode == nullptr) return;
    helperInorderTravel(treenode->left);
    processfunction(treenode->e);
    helperInorderTravel(treenode->right);
}

void Treap::postorderDelete(TreeNode *treenode) {
    if (treenode == nullptr) return;
    postorderDelete(treenode->left);
    postorderDelete(treenode->right);
    delete treenode;
}

void Treap::InorderTravel(ProcessElement f) {
    this->processfunction = f;
    helperInorderTravel(root);
    this->processfunction = nullptr;
}

Treap::~Treap() {
    postorderDelete(root);
}
